package 折纸问题;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 折纸问题 {
	public static void main(String[] args) {
		FoldPaper1 fl = new FoldPaper1();
		for (int i = 1; i < 6; i++) {
			System.out.println(Arrays.toString(fl.foldPaper(i)));
		}
	}

	public static class FoldPaper1 {
		public String[] foldPaper(int n) {
			int L = (int) Math.pow(2, n) - 1;
			String[] res = new String[L];
			add(res, (L + 1) / 2, L / 2, "down");
			return res;
		}

		public void add(String[] res, int n, int loc, String str) {
			if (n == 1)
				res[loc] = str;
			else {
				res[loc] = str;
				add(res, n / 2, loc - n / 2, "down");
				add(res, n / 2, loc + n / 2, "up");
			}
		}
	}

	/**
	 * 不需要构建二叉树，把中序遍历的过程写下来就行了
	 * 
	 * @author hest0
	 *
	 */
	public static class FoldPaper2 {
		// 构造完全二叉树
		public String[] foldPaper(int n) {
			List<String> list = new LinkedList<String>();
			fold(n, list, "down");
			String[] strs = new String[(int) (Math.pow(2, n) - 1)];
			return list.toArray(strs);
		}

		// 中序遍历
		public void fold(int n, List<String> list, String str) {
			if (n != 0) {
				fold(n - 1, list, "down");
				list.add(str);
				fold(n - 1, list, "up");
			}
		}
	}
}
